package com.mj.listen3.链表;

/**
 * https://leetcode-cn.com/problems/intersection-of-two-linked-lists/
 */
public class _160_相交链表 {
    /**
     * 思路比较好，不好想，但是推荐的写法
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) return null;
        ListNode curA = headA;
        ListNode curB = headB;
        while (curA != curB) {
            // 拼接上headB
            curA = curA == null ? headB : curA.next;
            // 拼接上headA
            curB = curB == null ? headA : curB.next;
        }
        return curA;
    }

    /**
     * 思路常规
     */
    public ListNode getIntersectionNode2(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) return null;
        ListNode cur1 = headA;
        ListNode cur2 = headB;
        int n = 0;
        // 找A的最后一个节点
        while (cur1.next != null) {
            // 注意判断 cur1.next != null 原因在于找出最后一个节点
            n++;
            cur1 = cur1.next;
        }

        // 找B的最后一个节点
        while (cur2.next != null) {
            // 注意判断 cur2.next != null 原因在于找出最后一个节点
            n--;
            cur2 = cur2.next;
        }

        // 判断是否相交
        if (cur1 != cur2) {
            // 如果相交最后一个节点一定相同
            return null;
        }

        // 相交，找相交节点
        cur1 = n > 0 ? headA : headB;
        cur2 = cur1 == headA ? headB : headA;

        // n 是两个链表的长度差值
        n = Math.abs(n);

        while (n > 0) {
            cur1 = cur1.next;
            n--;
        }

        // 一起往后遍历
        while (cur1 != cur2) {
            cur1 = cur1.next;
            cur2 = cur2.next;
        }

        return cur1;
    }
}
